package com.xq.algorithm.string;

import java.util.ArrayList;
import java.util.TreeSet;

/**
 * @author jltxseo
 *         Created by junlintianxia on 2017/07/10.
 */

public class StringAlgorithm {

    /**
     * 字符串空格的替换
     * 将一个字符串中的空格替换成“%20”。例如，当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。
     * @param str
     * @return
     */
    public String repacleSpace(StringBuffer str){
        if(str == null)return null;

        StringBuffer sb = new StringBuffer();
        for (int i=0; i < str.length(); i++){
            char c = str.charAt(i);
            if(c == ' '){
                str.replace(i,i+1,"%20");
            }
        }

        return str.toString();
    }


    //用于最后返回结果
    ArrayList<String> list  = new ArrayList<>();
    //遍历的时候来存储序列实现排序
    TreeSet<String> set = new TreeSet<>();

    /**
     * 全排列
     * @param str
     * @return
     * 输入一个字符串,按字典序打印出该字符串中字符的所有排列。
     * 例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。 结果请按字母顺序输出。
     */
    public ArrayList<String> Permutation(String str) {
        if(str==null || str.length()==0) return list;

        Permutation(str.toCharArray(),0);
        //容器转换
        list.addAll(set);
        return list;
    }


    public void Permutation(char[] s,int index){
        if(s==null ||s.length==0 || index<0 || index>s.length-1)  return ;
        if(index==s.length-1){//递归固定到最后一个位置，把该串加入集合
            set.add(new String(s));
        }else{//固定前index+1个字符，递归后面所有可能的子串
            for(int i = index;i<s.length;i++){
                swap(s,index,i);//交换一次形成一个子串
                Permutation(s,index+1);
                swap(s,i,index);//复原使下次循环产生下一个子串
            }
        }
    }

    public void swap(char[] s,int i,int j){
        char temp = s[i];
        s[i] = s[j];
        s[j] = temp;
    }

    /**
     * 翻转字符串
     * @param data
     * @param start
     * @param end
     */
    public static void reverse(char[] data,int start,int end){
        if(data == null || data.length < 1 || start < 0 || end > data.length || start > end){
            return;
        }

        while (start < end){
            char tmp = data[start];
            data[start++] = data[end];
            data[end--] = tmp;
        }
    }

    /**
     * Reverse Words in a String
     * 输入字符串”I am a student. ”,则输出”student. a am I”
     * @param data
     * @return
     * 算法思路:先整个字符串整体翻转一次，然后再分别翻转每一个单词（或者先分别翻转每一个单词，然后再整个字符串整体翻转一次），此时就能得到我们需要的结果了。
     */
    public static char[] reverseString(char[] data){
        if (data == null || data.length < 1){
            return data;
        }
        reverse(data,0,data.length - 1);// 首先全局逆转

        int start = 0;
        int end = 0;
        while (start < data.length){
            if(data[start] == ' '){  // 排除开头空格
                start++;
                end++;
            }else if (end == data.length || data[end] == ' '){ // 单词结束边界
                reverse(data,start,end - 1);
                end++;
                start = end;
            }else {
                end++;
            }
        }
        return data;
    }

    /**
     * 翻转字符串之二
     * Input: s = "abcdefg", k = 2
     * Output: "bacdfeg"
     * @param data
     * @param k
     * @return
     * 算法思路:
     *  每隔k隔字符，翻转k个字符，最后如果不够k个了的话，剩几个就翻转几个。
     *  比较直接的方法就是先用n／k算出来原字符串s能分成几个长度为k的字符串，
     *  然后开始遍历这些字符串，遇到2的倍数就翻转，翻转的时候注意考虑下是否已经到s末尾了
     */
    public static char[] reverseString2(char[] data, int k){
        if (data == null || k < 0 || k > data.length) {
            return data;
        }
        for (int i=0; i < data.length; i +=2 * k){
            reverse(data,i,Math.min(i + k,data.length) -1);
        }
        return data;
    }

    /**
     * 翻转字符串中的单词之三
     * Input: "Let's take LeetCode contest"
     * Output: "s'teL ekat edoCteeL tsetnoc"
     * @param data
     * @return
     * 首先我们来看使用字符流处理类stringstream     来做的方法，
     * 相当简单，就是按顺序读入每个单词进行翻转即可
     * 思路:
     * 用两个指针，分别指向每个单词的开头和结尾位置，确定了单词的首尾位置后，
     * 再用两个指针对单词进行首尾交换即可，有点像验证回文字符串的方法
     */
    public static char[] reverseString3(char[] data){
        if (data == null || data.length < 1){
            return data;
        }
        int start = 0;
        int end = 0;
        while (start < data.length){
            if(data[start] == ' '){  // 排除开头空格
                start++;
                end++;
            }else if (end == data.length || data[end] == ' '){ // 单词结束边界
                reverse(data,start,end - 1);
                end++;
                start = end;
            }else {
                end++;
            }
        }
        return data;
    }


    /**
     * 输入字符串”abcefg”和数字 2,该函数将返回左旋转 2 位得到的结”cdefgab”
     * @param data
     * @param n
     * @return
     */
    public static char[] leftRotateString(char[] data, int n) {
        if (data == null || n < 0 || n > data.length) {
            return data;
        }
        reverse(data, 0, data.length - 1);
        System.out.println(data);
        reverse(data, 0, data.length - n - 1);
        System.out.println(data);
        reverse(data, data.length - n, data.length - 1);
        return data;
    }

    public static boolean isPalidrome(String str){
        char[]ch=str.toCharArray();
        int len=ch.length;
        int i=0;int j=len-1;
        while(i<=j){
            if(ch[i++]==ch[j--]){
            }else{
                return false;
            }
        }
        return true;
    }
}
